package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * c
 * dp
 * 1771. 由子序列构造的最长回文串的长度
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/22 10:50
 */
public class LongestPalindrome {

    public static void main(String[] args) {
        LongestPalindrome test = new LongestPalindrome();

        // 5
//        String word1 = "cacb";
//        String word2 = "cbba";

        // 3
//        String word1 = "ab";
//        String word2 = "ab";

        // 0
//        String word1 = "aa";
//        String word2 = "bb";

        // 11
        String word1 = "ldgsvnsgpdvmj";
        String word2 = "qpaktmjafgkzszekng";

        int i = test.longestPalindrome(word1, word2);
        System.out.println(i);
    }


    public int longestPalindrome(String word1, String word2) {
        char[] cs1 = word1.toCharArray();
        char[] cs2 = new StringBuilder(word2).reverse().toString().toCharArray();
        int l1 = word1.length();
        int l2 = word2.length();
        int[][] arr = new int[l1 + 1][l2 + 1];
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (cs1[i - 1] == cs2[j - 1]) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                } else {
                    arr[i][j] = Math.max(arr[i][j - 1], arr[i - 1][j]);
                }
            }
        }
        int[][] hs1 = find(cs1);
        int[][] hs2 = find(cs2);
        int max = 0;
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
                if (arr[i][j] == 0) {
                    continue;
                }
                max = Math.max(max, (arr[i][j] << 1) + Math.max(hs1[i][l1 - 1], hs2[j][l2 - 1]));
            }
        }
        return max;
    }

    private int[][] find(char[] cs) {
        int length = cs.length;
        int[][] hs = new int[length + 1][length + 1];
        for (int i = length - 1; i >= 0; i--) {
            hs[i][i] = 1;
            for (int j = i + 1; j < length; j++) {
                if (cs[i] == cs[j]) {
                    hs[i][j] = hs[i + 1][j - 1] + 2;
                } else {
                    hs[i][j] = Math.max(hs[i + 1][j], hs[i][j - 1]);
                }
            }
        }
        return hs;
    }

}
